package com.arithmetic.basics;
/**
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
 *
 * 示例 1:
 *
 * 输入: s = "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 * 示例 2:
 *
 * 输入: s = "bbbbb"
 * 输出: 1
 * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 * 示例 3:
 *
 * 输入: s = "pwwkew"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
 *      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 * 提示：
 *
 * 0 <= s.length <= 5 * 104
 * s 由英文字母、数字、符号和空格组成
 *总体思路:
 * 遍历字符串，每次以 i 值记录，不回溯 i 值，用flag记录遍历过程找到的重复的字符的位置。
 * 如果遇到重复字符，i-flag 即为子串长度，此时flag重新定位到子串中重复字符的位置，i 继续往后遍历。
 * 这里length跟result记录长度。
 */
public class Day13 {

    public int lengthOfLongestSubstring(String s) {
        int i = 0; // 当前遍历位置
        int flag = 0; // 窗口起始位置
        int length = 0;
        int result = 0;
        while (i < s.length()) {
            // indexOf查找当前字符在窗口内是否出现过
            int pos = s.indexOf(s.charAt(i), flag);
            // 如果出现过，则更新最长长度result，并移动窗口起点flag到重复字符后一位
            if (pos < i) {
                if (length > result) {
                    result = length;
                }
                // 每次循环更新当前子串长度length和遍历指针i；
                if (result >= s.length() - pos - 1) {
                    return result;
                }
                // 最终返回最长无重复子串长度
                length = i - pos - 1;
                flag = pos + 1;
            }
            length++;
            i++;
        }
        return length;
    }

}


